package ljl.codetop;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class _139_word_break {

    /**
     * 超时喽？
     */
    static class test {

        // 我只能先来硬的了
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> set = new HashSet<>(wordDict);
            return test(s, 0, set);
        }
        boolean test(String s, int from, Set<String> set) {
            if (from == s.length()) return true;
            for (int i = from + 1; i <= s.length(); i++) {
                if (set.contains(s.substring(from, i))) {
                    // 这不能返回，还得试
                    if (test(s, i, set)) return true;
                }
            }
            return false;
        }
    }

    static class off {
        /**
         * 尝试只看代码发现看不懂
         */
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> wordDictSet = new HashSet<>(wordDict);
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }

    static class copy {
        public boolean wordBreak(String s, List<String> wordDict) {
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i <= s.length() ; i++) {
                for (int j = i - 1; j >= 0 ; j--) {
                    if (dp[j] && wordDict.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }
}
